import random

from typing import List
from collections import Counter

def quicksort(cnt_nums, k):
    _, p = random.choice(cnt_nums)
    small, equal, big = [], [], []
    for x, c in cnt_nums:
        if c < p:
            small.append((x, c))
        elif c > p:
            big.append((x, c))
        else:
            equal.append((x, c))
    if len(big) == k:
        return big
    elif len(big) + len(equal) == k:
        return big + equal
    elif len(big) > k:
        return quicksort(big, k)
    else:
        return big + quicksort(small+equal, k-len(big))

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt_nums = Counter(nums)
        cnt_nums = list(cnt_nums.items())
        top_k = quicksort(cnt_nums, k)
        return [item[0] for item in top_k]

def load_test_data(file_name):
    with open(file_name, 'r') as file:
        test_data = eval(file.read())
    return test_data

def test_solution():
    solution = Solution()
    test_data = load_test_data('test_data.txt')
    k = 5  # 可以调整k的值进行不同的测试
    result = solution.topKFrequent(test_data, k)
    print(f"Top {k} frequent elements: {result}")

if __name__ == "__main__":
    test_solution()